package com.chj.jz.dp.class03;

import java.util.Arrays;
import java.util.Comparator;

public class Code11_RussianDollEnvelopes {
	 /**
     * @param envelopes: a number of envelopes with widths and heights
     * @return: the maximum number of envelopes
     */
    public static int maxEnvelopes(int[][] envelopes) {
        // write your code here
    	if(envelopes == null || envelopes.length == 0) {
    		return 0;
    	}
    	
    	Arrays.sort(envelopes, new Comparator<int[]>() {
    		public int compare(int[] a, int[] b) {
    			if(a[0] == b[0]) {
    				return a[1] - b[1];
    			}else {
    				return a[0] - b[0];
    			}
    		}
    	});
    	
    	int n = envelopes.length;
    	int[] f = new int[n];
    	int i, j, res = 0;
    	for(i = 0; i < n; i++) {
    		f[i] = 1;
    		
    		for(j = 0; j < i; j++) {
    			if(envelopes[j][0] < envelopes[i][0] && envelopes[j][1] <  envelopes[i][1]) {
    				f[i] = Math.max(f[i], f[j] + 1);
    			}
    		}
    		
    		res = Math.max(res, f[i]);
    	}
    	
    	return res;
    }
    
	public static void main(String[] args) {
		{
			int[][] arr = new int[][] {{5,4},{6,4},{6,7},{2,3} };
			System.out.println(maxEnvelopes(arr));
		}
		{
			int[][] arr = new int[][] { {4,5},{4,6},{6,7},{2,3},{1,1}};
			System.out.println(maxEnvelopes(arr));
		}
		// {
		// int[] arr = new int[] { 1, 2, 3, 4, 5 };
		// System.out.println(maxProfitIII(arr));
		// }
		// {
		// int[] arr = new int[] { 5, 4, 3, 2, 1 };
		// System.out.println(maxProfitIII(arr));
		// }

	}
}
